#########################################################################
#									#
# Titulo: Algoritmo Genetico para Minimizacao de um Paraboloide		#
#									#
# Descricao: A partir de um intervalo continuo entre -100 e 100, esse	#
#	     programa tem a meta de utilizar um algoritmo de otimizacao,#
#	     o qual eh o Algoritmo Genetico, para encontrar o minimo	#
#	     global de uma superficie paraboloide caracterizada pela	#
#	     funcao f(x,y) = x*x = y*y					#
#									#
# Autores: Jailton Maciel						#
#	   Julio Cesar							#
# 									#
# Data da ultima modificacao: 11/07/2011				#
#									#
#########################################################################

#########################################################################
#
# Area de dados
#
.data

TAMANHO_POPULACAO: .word 20
NUM_GENES: .word 2
NUM_VARIAVEIS_POPULACAO: .word 40
NUM_ITERACOES: .word 50
LIMITE_INF: .double -100.0
LIMITE_SUP: .double 100.0

populacao: .double 0 : 40
populacaoTemp: .double 0 : 40

space:.asciiz  " "
linha: .asciiz "\n"

#########################################################################
#
# Area do programa
#
.text

#########################################################################
#
# MAIN
#
main:
	# seta os limites
	la $t0, LIMITE_INF
	la $t1, LIMITE_SUP
	l.d $f28, 0($t0)
	l.d $f30, 0($t1)
	
	# chamadas do programa
	jal gera_populacao_inicial
	jal iteracao
	jal imprime
	
	# finaliza o programa com sucesso
	j saida
	

#########################################################################
#
# Procedimento que realiza N iteracoes do algoritmo genetico
# Entrada: void
# Saida: void
#
iteracao:
	# salva os valores correntes dos registrados na pilha para serem restaurados posteriormente
	addi $sp, $sp, -4			# empilha registradores
	sw $ra, 0($sp)
	
	# loop que controla o numero de iteracoes
	la $t0, NUM_ITERACOES
	lw $s0, 0($t0)
	move $s1, $zero
	loop_iteracao:
		blt $s1, $s0, in_loop_iteracao
		bge $s1, $s0, out_loop_iteracao
		
		# laco de execucao do numero de iteracoes
		in_loop_iteracao:
			
			# realiza elitismo de 2 individuos
			addi $t0, $zero, 2
			move $t1, $zero
			la $t2, populacao
			la $t3, populacaoTemp
			loop_elitismo:
				blt $t1, $t0, in_loop_elitismo
				bge $t1, $t0, out_loop_elitismo
			
				# laco de execucao do elitismo
				in_loop_elitismo:
					l.d $f2, 0($t2)
					s.d $f2, 0($t3)
					l.d $f2, 8($t2)
					s.d $f2, 8($t3)
					addi $t2, $t2, 16
					addi $t3, $t3, 16
			
					addi $t1, $t1, 1
					j loop_elitismo
					
				# fim do loop da operacao de elitismo
				out_loop_elitismo:
			
			# chamada do crossover
			addi $t0, $zero, 12
			addi $t1, $zero, 2
			loop_crossover:
				blt $t1, $t0, in_loop_crossover
				bge $t1, $t0, out_loop_crossover
				
				# laco de execucao do crossover
				in_loop_crossover:
					# obtem o indice de um individuo selecionado
					jal roleta_rank
					move $t4, $a0
					# seleciona outro individuo com indice diferente
					loop_igualdade_indice:
						jal roleta_rank
						move $t5, $a0
						beq $t4, $t5, loop_igualdade_indice
					# chama o procedimento de crossover
					move $a0, $t1
					addi $a1, $t1, 1
					move $a2, $t4
					move $a3, $t5
					jal operador_crossover
					addi $t1, $t1, 2
					j loop_crossover
				
				# fim do loop da operacao de crossover
				out_loop_crossover:
		
			# chamada da mutacao
			addi $t0, $zero, 20
			addi $t1, $zero, 12
			loop_mutacao:
				blt $t1, $t0, in_loop_mutacao
				bge $t1, $t0, out_loop_mutacao
				
				# laco de execucao da mutacao
				in_loop_mutacao:
					la $t2, TAMANHO_POPULACAO
					lw $t3, 0($t2)
					
					# escolhe o individuo aleatoriamente
					move $a1, $t3
					li $v0, 42
					syscall
					
					# chama o procedimento de mutacao
					move $a1, $t1
					jal operador_mutacao
					
					addi $t1, $t1, 1
					j loop_mutacao
				
				# fim do loop da operacao de mutacao
				out_loop_mutacao:
			
			# populacao <-- populacaoTemp
			addi $t0, $zero, 20
			move $t1, $zero
			la $t2, populacao
			la $t3, populacaoTemp
			loop_atualiza_populacao:
				blt $t1, $t0, in_loop_atualiza_populacao
				bge $t1, $t0, out_loop_atualiza_populacao
				
				in_loop_atualiza_populacao:
					l.d $f2, 0($t3)
					s.d $f2, 0($t2)
					l.d $f2, 8($t3)
					s.d $f2, 8($t2)
					addi $t2, $t2, 16
					addi $t3, $t3, 16
			
					addi $t1, $t1, 1
					j loop_atualiza_populacao
				
				out_loop_atualiza_populacao:
				
			# ordenacao da populacao
			jal bubble_sort
			
		# incrementa o contador do numero de iteracoes
		addi $s1, $s1, 1
		j loop_iteracao
		
		out_loop_iteracao:
	
		
	# carrega os antigos valores dos registradores
	lw $ra, 0($sp)
	addi $sp, $sp, 4			# desempilha registradores
			
	# retorna para onde foi chamado	
	jr $ra
		

#########################################################################
#
# Procedimento que realiza a mutacao de um individuo
# Entrada: indice escolhido para realizar mutacao
# Saida: void
#
operador_crossover:
	# salva os valores correntes dos registrados na pilha para serem restaurados posteriormente
	addi $sp, $sp, -36		# empilha registradores
	sw $ra, 0($sp)
	sw $t0, 4($sp)
	sw $t1, 8($sp)
	sw $t2, 12($sp)
	sw $t3, 16($sp)
	sw $t4, 20($sp)
	sw $t5, 24($sp)
	swc1 $f2, 28($sp)
	swc1 $f3, 32($sp)

	# endereco...
	la $t0, populacao
	la $t1, populacaoTemp
	
	#offset...
	mul $t2, $a0, 16
	mul $t3, $a1, 16
	mul $t4, $a2, 16
	mul $t5, $a3, 16
		
	# populacaoTemp[indexFilho1][0] = populacao[indexPai1][0]
	add $t4, $t0, $t4
	add $t2, $t1, $t2
	l.d $f2, 0($t4)
	s.d $f2, 0($t2)
	
	#populacaoTemp[indexFilho1][1] = populacao[indexPai2][1]
	add $t5, $t0, $t5
	add $t3, $t1, $t3
	l.d $f2, 0($t5)
	s.d $f2, 0($t3)
	
	# populacaoTemp[indexFilho2][0] = populacao[indexPai2][0]
	addi $t2, $t2, 8
	addi $t3, $t3, 8
	addi $t4, $t4, 8
	addi $t5, $t5, 8
	
	# populacaoTemp[indexFilho2][1] = populacao[indexPai1][1]
	l.d $f2, 0($t4)
	s.d $f2, 0($t3)
	l.d $f2, 0($t5)
	s.d $f2, 0($t2)
	
	# carrega os antigos valores dos registradores
	lw $ra, 0($sp)
	lw $t0, 4($sp)
	lw $t1, 8($sp)
	lw $t2, 12($sp)
	lw $t3, 16($sp)
	lw $t4, 20($sp)
	lw $t5, 24($sp)
	lwc1 $f2, 28($sp)
	lwc1 $f3, 32($sp)
	addi $sp, $sp, 36		# desempilha registradores
	
	# retorna para onde foi chamado	
	jr $ra
	

#########################################################################
#
# Procedimento que realiza a mutacao de um individuo
# Entrada: indice escolhido para realizar mutacao
# Saida: void
#
operador_mutacao:
	# salva os valores correntes dos registrados na pilha para serem restaurados posteriormente
	addi $sp, $sp, -28		# empilha registradores
	sw $ra, 0($sp)
	sw $t0, 4($sp)
	sw $t1, 8($sp)
	sw $t2, 12($sp)
	sw $t3, 16($sp)
	swc1 $f0, 20($sp)
	swc1 $f1, 24($sp)
	
	la $t0, populacao
	la $t1, populacaoTemp
	
	# offset...
	mul $t2, $a0, 16
	mul $t3, $a1, 16
	
	add $t2, $t0, $t2
	add $t3, $t1, $t3
	
	# random de qual variavel vai realizar a mutacao
	addi $a1, $zero, 2
	li $v0, 42
	syscall
		
	bnez $a0, if_mutacao
	beqz $a0, else_mutacao
	
	if_mutacao:
		li $v0, 44 		# random para double: 0 <= x <= 1
		syscall
		
		# populacaoTemp[i][0] = mutacao(populacao[i][0])
		# populacaoTemp[i][1] = populacao[i][1] 
		sub.d $f2, $f30, $f28
		mul.d $f0, $f0, $f2
		add.d $f0, $f0, $f28
		s.d $f0, 0($t3)
		l.d $f0, 8($t2)
		s.d $f0, 8($t3)
		j fim_if
	
	else_mutacao:
		li $v0, 44 		# random para double: 0 <= x <= 1
		syscall
		
		# populacaoTemp[i][0] = populacao[i][0]
		# populacaoTemp[i][1] = mutacao(populacao[i][1])
		sub.d $f2, $f30, $f28
		mul.d $f0, $f0, $f2
		add.d $f0, $f0, $f28
		s.d $f0, 8($t3)
		l.d $f0, 0($t2)
		s.d $f0, 0($t3)
		j fim_if
		
	fim_if:
		# carrega os antigos valores dos registradores
		lw $ra, 0($sp)
		lw $t0, 4($sp)
		lw $t1, 8($sp)
		lw $t2, 12($sp)
		lw $t3, 16($sp)
		lwc1 $f0, 20($sp)
		lwc1 $f1, 24($sp)
		addi $sp, $sp, 28		# desempilha registradores
	
		# retorna para onde foi chamado	
		jr $ra
		

#########################################################################
#
# Procedimento que retorna o indice de um individuo selecionado pela roleta ranqueada
# Entrada: void
# Saida: $a0 - indice do individuo selecionado
#
roleta_rank:
	# salva os valores correntes dos registrados na pilha para serem restaurados posteriormente
	addi $sp, $sp, -36		# empilha registradores
	sw $ra, 0($sp)
	sw $t0, 4($sp)
	sw $t1, 8($sp)
	sw $t2, 12($sp)
	sw $t3, 16($sp)
	sw $t4, 20($sp)
	sw $t5, 24($sp)
	sw $t6, 28($sp)
	sw $t7, 32($sp)
	
	# calcula a soma das particoes da roleta
	la $t0, TAMANHO_POPULACAO
	lw $t1, 0($t0)
	addi $t2, $t1, 1
	mul $t1, $t1, $t2
	div $t1, $t1, 2
	
	# sorteia na roleta
	add $a1, $zero, $t1
	li $v0, 42
	syscall
	move $t2, $a0
	
	move $t3, $zero
	move $t4, $zero
	lw $t5, 0($t0)
	addi $t6, $t5, -1
	loop_rank:
		#  for(int j = TAM_POPULACAO; (i < TAM_POPULACAO-1) && (aux < pontoRoleta); ++i, --j)
		slt $t0, $t4, $t6
		slt $t7, $t3, $t2
		and $t7, $t0, $t7
		beq $t7, 1, no_laco
		bne $t7, 1, sai_laco
		
		no_laco:
			add $t3, $t3, $t5		# aux += j
			addi $t5, $t5, -1
			addi $t4, $t4, 1
			j loop_rank
		# seta o indice para retorno
		sai_laco:
			move $a0, $t4
		
	# carrega os antigos valores dos registradores
	lw $ra, 0($sp)
	lw $t0, 4($sp)
	lw $t1, 8($sp)
	lw $t2, 12($sp)
	lw $t3, 16($sp)
	lw $t4, 20($sp)
	lw $t5, 24($sp)
	lw $t6, 28($sp)
	lw $t7, 32($sp)
	addi $sp, $sp, 36		# desempilha registradores
	
	# retorna para onde foi chamado		
	jr $ra
	
	
#########################################################################
#
# Procedimento que imprime os valores das variaveis de um individuo
# Entrada: void
# Saida: void
#
imprime:
	# salva os valores correntes dos registrados na pilha para serem restaurados posteriormente
	addi $sp, $sp, -4		# empilha registradores
	sw $ra, 0($sp)
	
	addi $t0, $zero, 1
	addi $t1, $zero, 0
	la $t2, populacao
	loop_imprime:
		# imprime a variavel populacao[i][0]
		l.d $f12, 0($t2)
		li $v0, 3
		syscall
		
		# imprime o caractere de espaco
		la $a0, space
		li $v0, 4
		syscall 
		
		# imprime a variavel populacao[i][1]
		l.d $f12, 8($t2)
		li $v0, 3
		syscall
		
		# imprime o caractere de quebra de linha
		la $a0, linha
		li $v0, 4
		syscall
		
		# controle do loop
		addi $t2, $t2, 16
		addi $t1, $t1, 1
		blt $t1, $t0, loop_imprime
		
	# carrega os antigos valores dos registradores
	lw $ra, 0($sp)
	addi $sp, $sp, 4		# desempilha registradores
		
	# retorna para onde foi chamado
	jr $ra
		

#########################################################################
#
# Procedimento que gera a populacao inicial do algoritmo genetico
# Entrada: void
# Saida: void
#
gera_populacao_inicial:
	# salva os valores correntes dos registrados na pilha para serem restaurados posteriormente
	addi $sp, $sp, -4		# empilha registradores
	sw $ra, 0($sp)
	
	# for(int i = 0; i < NUM_VARIAVEIS_POPULACAO; ++i)
	la $t0, NUM_VARIAVEIS_POPULACAO
	la $t7, populacao
	lw $t1, 0($t0)			 # $t1 = NUM_VARIAVEIS_POPULACAO
	loop_gera_populacao_inicial: 
		# random para double: 0 <= x <= 1
		li $v0, 44
		syscall
		
		# mantem o valor gerado entre LIMITE_INF e LIMITE_SUP
		sub.d $f2, $f30, $f28
		mul.d $f0, $f0, $f2
		add.d $f0, $f0, $f28
		s.d $f0, 0($t7)
		
		# controle do loop e do indice
		addi $t7, $t7, 8
		addi $t1, $t1, -1
		bgtz $t1, loop_gera_populacao_inicial
	
	# ordena, baseado na fitness, a populacao gerada aleatoriamente
	jal bubble_sort
	
	# carrega os antigos valores dos registradores
	lw $ra, 0($sp)
	addi $sp, $sp, 4		# desempilha registradores
	
	# retorna para onde foi chamado
	jr $ra


#########################################################################
#
# Procedimento que ordena os individos da populacao diante ao valor da fitness de cada um
# Utiliza o algoritmo de ordenacao Bubblesort
# Entrada: void
# Saida: void
#
bubble_sort:
	# salva os valores correntes dos registrados na pilha para serem restaurados posteriormente
	addi $sp, $sp, -36			# empilha registradores
	sw $ra, 0($sp)
	sw $t0, 4($sp)
	sw $t1, 8($sp)
	sw $t2, 12($sp)
	sw $t3, 16($sp)
	swc1 $f2, 20($sp)
	swc1 $f3, 24($sp)
	swc1 $f4, 28($sp)
	swc1 $f5, 32($sp)
	
	# Loop1 do Bubble Sort
	la $t0, TAMANHO_POPULACAO
	lw $t1, 0($t0)
	loop1_bubble_sort:
		
		# Loop2 do Bubble Sort
		addi $t2, $zero, 1
		loop2_bubble_sort:
			addi $t3, $t2, -1
			# Calcula a fitness do individuo de indice $t3
			move $a0, $t3
			jal fitness
			mov.d $f2, $f0
			
			# Calcula a fitness do individuo de indice $t2
			move $a0, $t2
			jal fitness
			mov.d $f4, $f0
			
			# Compara a fitness dos individuos de indices $t3 e $t2
			c.le.d $f2, $f4
			bc1f if1_bubble_sort	# True se a fitness do individuo de indice $t3 eh menor 
			bc1t if2_bubble_sort	# False se a fitness do individuo de indice $t3 maior-igual 
			
			# realiza o swap
			if1_bubble_sort:
				move $a0, $t3
				move $a1, $t2
				jal swap
			# incrementa $t2 ate atingir $t1
			if2_bubble_sort:
				addi $t2, $t2, 1
				blt $t2, $t1, loop2_bubble_sort
		
		# decrementa $t1 ate sair do loop
		addi $t1, $t1, -1
		bge $t1, 1, loop1_bubble_sort
	
	# carrega os antigos valores dos registradores
	lw $ra, 0($sp)
	lw $t0, 4($sp)
	lw $t1, 8($sp)
	lw $t2, 12($sp)
	lw $t3, 16($sp)
	lwc1 $f2, 20($sp)
	lwc1 $f3, 24($sp)
	lwc1 $f4, 28($sp)
	lwc1 $f5, 32($sp)
	addi $sp, $sp, 36			# desempilha registradores
	
	# retorna para onde foi chamado
	jr $ra


#########################################################################
#
# Procedimento que realiza o swap entre 2 individuos em uma sequencia
# Entrada: $a0 - indice do individuo A | $a1 - indice do individuo B
# Saida: void
#
swap:
	# salva os valores correntes dos registrados na pilha para serem restaurados posteriormente
	addi $sp, $sp, -44	# empilha registradores
	sw $ra, 0($sp)
	sw $t1, 4($sp)
	sw $t2, 8($sp)
	swc1 $f2, 12($sp)
	swc1 $f3, 16($sp)
	swc1 $f4, 20($sp)
	swc1 $f5, 24($sp)
	swc1 $f6, 28($sp)
	swc1 $f7, 32($sp)
	swc1 $f8, 36($sp)
	swc1 $f9, 40($sp)
	
	# atinge o endereco dos individuos a partir do offset deles
	mul $t1, $a0, 16	# $t1 = endereco de populacao[$a0]
	mul $t2, $a1, 16	# $t2 = endereco de populacao[$a1]
	
	# carrega os valores do individuo A
	l.d $f2, populacao($t1)	# $f2 = populacao[$a0][0]
	addi $t1, $t1, 8
	l.d $f4, populacao($t1)	# $f4 = populacao[$a0][1]
	
	# carrega os valores do individuo B
	l.d $f6, populacao($t2)	# $f6 = populacao[$a1][0]
	addi $t2, $t2, 8
	l.d $f8, populacao($t2)	# $f8 = populacao[$a1][1]
	
	# volta para o endereco inicial dos individuos
	addi $t1, $t1, -8
	addi $t2, $t2, -8
	
	# armazena o individuo A na antiga posicao do individuo B
	s.d $f2, populacao($t2)	# populacao[$a1][0] = $f2
	addi $t2, $t2, 8
	s.d $f4, populacao($t2)	# populacao[$a1][1] = $f4
	
	# armazena o individuo B na antiga posicao do individuo A
	s.d $f6, populacao($t1)	# populacao[$a0][0] = $f6
	addi $t1, $t1, 8
	s.d $f8, populacao($t1)	# populacao[$a0][1] = $f8
	
	# carrega os antigos valores dos registradores
	lw $ra, 0($sp)
	lw $t1, 4($sp)
	lw $t2, 8($sp)
	lwc1 $f2, 12($sp)
	lwc1 $f3, 16($sp)
	lwc1 $f4, 20($sp)
	lwc1 $f5, 24($sp)
	lwc1 $f6, 28($sp)
	lwc1 $f7, 32($sp)
	lwc1 $f8, 36($sp)
	lwc1 $f9, 40($sp)
	addi $sp, $sp, 44	# desempilha registradores
	
	# retorna para onde foi chamado
	jr $ra


#########################################################################
#
# Procedimento que calcula a fitness do individuos (funcao de avaliacao)
# Entrada: $a0 - indice do individuo
# Saida: $f0 - resultado da fitness
#
fitness:
	# salva os valores correntes dos registrados na pilha para serem restaurados posteriormente
	addi $sp, $sp, -40	# empilha registradores
	sw $ra, 0($sp)
	sw $t0, 4($sp)
	sw $t1, 8($sp)
	sw $t2, 12($sp)
	swc1 $f2, 16($sp)
	swc1 $f3, 20($sp)
	swc1 $f4, 24($sp)
	swc1 $f5, 28($sp)
	swc1 $f6, 32($sp)
	swc1 $f7, 36($sp)
	
	# acessa o individuo atraves do indice
	la $t0, populacao 	# acessa o vetor populacao
	mul $t1, $a0, 16 	# obtem o indice para realizar: populacao[i][0]
	addi $t2, $t1, 8 	# obtem o indice para realizar: populacao[i][1]
	l.d $f2, populacao($t1) # $f2 = populacao[i][0]
	l.d $f4, populacao($t2)	# $f3 = populacao[i][1]
	
	# fitness = x*x + y*y
	mul.d $f2, $f2, $f2 	# $f2 = populacao[i][0]*populacao[i][0]
	mul.d $f4, $f4, $f4 	# $f4 = populacao[i][1]*populacao[i][1]
	add.d $f6, $f2, $f4 	# $f6 = $f2 + $f4
	mov.d $f0, $f6		# $f0 = $f6 para o valor retornado fica em $f0
	
	# carrega os antigos valores dos registradores
	lw $ra, 0($sp)
	lw $t0, 4($sp)
	lw $t1, 8($sp)
	lw $t2, 12($sp)
	lwc1 $f2, 16($sp)
	lwc1 $f3, 20($sp)
	lwc1 $f4, 24($sp)
	lwc1 $f5, 28($sp)
	lwc1 $f6, 32($sp)
	lwc1 $f7, 36($sp)
	addi $sp, $sp, 40	# desempilha registradores
	
	# retorna para onde foi chamado
	jr $ra
	
	
#########################################################################
#
# Chamada que finaliza o programa
#
saida:
	li $v0, 10
	syscall
